from typing import List


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        size = len(rods)

        # 处理钢筋数量少于2根的情况
        if size < 2:
            return 0

        # 按长度倒序排序钢筋
        rods.sort(reverse=True)

        # 计算每个钢筋之后的钢筋总长度（后缀和）
        surplus = [0] * size
        surplus[-1] = rods[-1]
        for i in range(size - 2, -1, -1):
            surplus[i] = surplus[i + 1] + rods[i]

        # 计算单侧可能的极限最大高度
        max_height = sum(rods) // 2

        ans = 0

        dp1 = {(0, 0)}
        for i in range(size):
            dp2 = set()
            rod = rods[i]
            for l1, r1 in dp1:
                # [剪枝1]剩余的钢筋已不足以支持当前情况超过当前最优解
                if l1 + r1 + surplus[i] <= ans * 2:
                    continue

                # [剪枝4]剩余的钢筋已不足以支持将两侧高度拉平
                if max(l1, r1) - min(l1, r1) > surplus[i]:
                    continue

                # 【选择1】不使用当前钢筋
                dp2.add((l1, r1))

                # 【选择2】将当前钢筋用到左侧
                l2, r2 = l1 + rod, r1

                # [剪枝2]避免左侧钢筋长度超过极限最大高度
                if l2 <= max_height:
                    if l2 == r2:
                        ans = max(ans, l2)
                    dp2.add((l2, r2))

                # 【选择3】将当前钢筋用到右侧
                l2, r2 = l1, r1 + rod

                # [剪枝3]避免右侧钢筋长度超过极限最大高度
                if r2 <= max_height:
                    if l2 == r2:
                        ans = max(ans, l2)
                    dp2.add((l2, r2))

            dp1 = dp2

        return ans


if __name__ == "__main__":
    print(Solution().tallestBillboard([1, 2, 3, 6]))  # 6
    print(Solution().tallestBillboard([1, 2, 3, 4, 5, 6]))  # 10
    print(Solution().tallestBillboard([1, 2]))  # 0
